package cn.edu.anan.datastructure.skiptable;

/**
 * 跳表实现：
 *  1.思想
 *      1.1.用空间换时间
 *      1.2.通过单链表实现，且要求链表存储有序
 *  2.时间复杂度
 *      O(logn)
 *  3.空间复杂度
 *      O(n)
 */
public class SkipList{

    // 索引最大层级
    public static final int MAX_LEVEL = 16;
    // 插入元素时，更新层级概率
    public static final float SKIP_LIST_P = 0.5f;

    // 索引层级从1开始
    public int levelCount = 1;

    // 带头链表
    public Node head = new Node();

    /**
     * 查找
     * @param value
     * @return
     */
    public Node find(int value){
        // 从头节点开始查找
        Node p = head;
        // 从最大层开始循环遍历（纵向向下）
        for(int i = levelCount -1 ; i >= 0; --i){
            // 判断比较下一个节点：
            // 如果不为空，且数据小于目标值value，则横向向前移动
            // 如果不为空，且数据大于等于目标值value，则纵向向下移动
            while (p.forwards[i] != null &&
                    p.forwards[i].data < value){
                p = p.forwards[i];
            }
        }

        // 所有层级遍历结束,得到原始链表第一个大于等于目标值value的节点
        if(p.forwards[0] != null &&
                p.forwards[0].data == value){
            return p.forwards[0];
        }else{
            return null;
        }

    }

    /**
     * 插入
     * @param value
     */
    public void insert(int value){
        // 新元素，需要插入的层级
        int level = randomLevel();

        // 创建新元素节点
        Node newNode = new Node();
        newNode.data = value;
        newNode.maxLevel = level;

        // 存储新节点所有层数上，各自的前一个节点的信息
        Node[] updates = new Node[level];
        for(int i = 0; i < level; ++i){
            updates[i] = head;
        }

        // update[i]记录每一层，小于目标值value的最大值
        Node p = head;
        for(int i = level - 1; i >= 0; --i){
            while (p.forwards[i] != null &&
                    p.forwards[i].data < value){
                p = p.forwards[i];
            }
            updates[i] = p;
        }

        // 循环遍历每一层，调整指针指向，完成新元素插入
        for(int i = 0; i < level; i++){
            newNode.forwards[i] = updates[i].forwards[i];
            updates[i].forwards[i] = newNode;
        }

        // 更新节点高度
        if(levelCount < level){
            levelCount = level;
        }

    }

    /**
     * 删除
     * @param value
     */
    public void delete(int value) {
        // 查找删除节点所有层数上，各自的前一个节点的信息
        Node[] updates = new Node[levelCount];
        Node p = head;
        for(int i = levelCount - 1; i >= 0; --i){
            while (p.forwards[i] != null &&
                    p.forwards[i].data < value){
                p = p.forwards[i];
            }

            updates[i] = p;
        }

        // 改变删除节点，前一个节点updates[i]的指针，指向删除节点的下一个节点
        if(p.forwards[0] != null &&
                p.forwards[0].data == value){
            for(int i = levelCount - 1; i >= 0; --i){
                if(updates[i].forwards[i] != null &&
                        updates[i].forwards[i].data == value){
                    updates[i].forwards[i] = updates[i].forwards[i].forwards[i];
                }
            }
        }

        // 跳转索引层级
        while (levelCount > 1 &&
                head.forwards[levelCount] == null){
            levelCount --;
        }

    }

    /**
     * 打印跳表
     */
    public void printAll(int level) {
        Node p = head;
        while (p.forwards[level] != null ){
            System.out.print(p.forwards[level] + " ");
            p = p.forwards[level];
        }
        System.out.println();
    }

    /**
     * 思考（每两个元素，抽取一个建立索引）：
     *  1.理论来讲:
     *      1.1.一级索引中元素个数应该占原始数据的：50%
     *      1.2.二级索引中元素个数占：25%
     *      1.3.三级索引中元素个数占：12.5%
     *      1.4.一直到最顶层MAX_LEVEL：......
     *  2.因为这里每一层的晋升概率是 50%：
     *      2.1.对于每一个新插入的节点
     *      2.2.都需要调用 randomLevel 生成一个合理的层数
     *  3.randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数：
     *      3.1.50%的概率返回 1
     *      3.2.25%的概率返回 2
     *      3.3.12.5%的概率返回 3...
     *
     * @return
     */
    private int randomLevel(){
        // 初始第一层插入新元素
        int level = 1;
        /**
         * 1.SKIP_LIST_P等于0.5f，表示50%概率
         * 2.Math.random()会产生0.0f-1.0f的数字
         * 3.每通过一次循环：level加1
         * 4.表示第level+1层插入新元素概率：从50%、25%、12.5%...依次递减
         * 5.最终的目的：保障跳表是一个理想的跳表，即每一层的元素个数，是下一层的1/2
         */
        while(Math.random() < SKIP_LIST_P &&
                level < MAX_LEVEL){

            level += 1;
        }

        return level;
    }

    /**
     * 节点封装
     */
    public class Node{
        // 节点数据
        private int data = -1;
        // 节点最大层级
        private int maxLevel = 0;

        // 横向、纵向指针（存储该节点所有层的下一个节点的信息）
        private Node[] forwards = new Node[MAX_LEVEL];

        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("{ data: ");
            builder.append(data);
            builder.append("; levels: ");
            builder.append(maxLevel);
            builder.append(" }");

            return builder.toString();
        }

    }

}